package nachos.vm;

import java.util.Random;

import org.omg.PortableServer.POA;

import nachos.machine.*;
import nachos.threads.*;
import nachos.userprog.*;
import nachos.vm.*;

/**
 * A kernel that can support multiple demand-paging user processes.
 */
public class VMKernel extends UserKernel {
    /**
     * Allocate a new VM kernel.
     */
    public VMKernel() {
	super();
    }

    /**
     * Initialize this kernel.
     */
    public void initialize(String[] args) {
	super.initialize(args);
	
	phyPages = new VMProcess[numPhysPages];
	phyPagesvpn = new int[numPhysPages];
	mainmemLock = new Lock();
//	pinLock = new Lock();
	
	swap = new Swap();
	random = new Random();
	tlbSize = Machine.processor().getTLBSize();
	
	pinWaiter = new PinWaiter();
	
    }

    /**
     * Test this kernel.
     */	
    public void selfTest() {
	super.selfTest();
    }

    /**
     * Start running user programs.
     */
    public void run() {
	super.run();
    }
    
    /**
     * Terminate this kernel. Never returns.
     */
    public void terminate() {
    	swap.cleanUp(); 
    	super.terminate();
    }

    // dummy variables to make javac smarter
    private static VMProcess dummy1 = null;

    private static final char dbgVM = 'v';
    private static final char dbgProcess = 'a';
    public static Swap swap;
    
    
    public static Lock mainmemLock;
//    public static Lock pinLock;
    private static VMProcess[] phyPages;
    private static int[] phyPagesvpn;
    
    private static void printPhyPage() {
    	Lib.debug(dbgVM, "----------------- Phy pages --------------------");
    	for (int i=0;i<numPhysPages;i++) {
    		if (phyPages[i] != null) {
    			Lib.debug(dbgVM, "ppn: "+i+" process name:" +phyPages[i]+" vpn:"+phyPagesvpn[i]);
    			
    		}
    	}
    	Lib.debug(dbgVM, "-----------------    end    --------------------");
    }
    
    /**
     * 
     * @param process the caller
     * @param vpn
     * @return ppn -1 on error
     */
    public static int getPhyPage(VMProcess process, int vpn) {
    	Lib.debug(dbgVM, "Process "+process+" request phy page for vpn "+vpn);
//    	printPhyPage();
//    	pageTableLock.acquire();
    	// try to find a free phy page
    	for (int i=0;i<numPhysPages;i++) {
    		if (phyPages[i] == null) {
    			// got a free page
    			phyPages[i] = process;
    			phyPagesvpn[i] = vpn;
//    			pageTableLock.release();
    			Lib.debug(dbgVM, "It get ppn:" + i);
    	    	printPhyPage();
    			return i;
    		}
    	}
    	// no any free page, run clock ALG to evict one page
    	
    	// before run clock, write current TLB back to current process's page table
    	for (int i=0 ; i<tlbSize ; i++) {
			TranslationEntry tlbEntry = Machine.processor().readTLBEntry(i);
			if (tlbEntry.valid) {
				ExtendedTransEntry ete = process.getETE(tlbEntry.vpn);
				if (tlbEntry.used) {
					ete.translationEntry.used = true;
				}
				if (tlbEntry.dirty) {
					ete.translationEntry.dirty = true;
				}
			}
		}

    	int ppn = clock();
    	phyPages[ppn] = process;
		phyPagesvpn[ppn] = vpn;
//    	pageTableLock.release();
    	Lib.debug(dbgVM, "It get ppn:" + ppn);
    	printPhyPage();
    	return ppn;
    }
    
    /**
     * 
     * @return the new free page number, ppn
     */
    private static int clock() {
    	
    	for(int j = clockLastPos + 1 ; j<numPhysPages+clockLastPos+1;j++) {
    		int i = j%numPhysPages;
    		VMProcess process = phyPages[i];
    		int vpn = phyPagesvpn[i];
    		TranslationEntry translationEntry = process.getETE(vpn).translationEntry;
    		if (!translationEntry.used) {
    			// not used, not pinned, evict this page
    			if (!process.getETE(vpn).isPinned) {
    				process.evictPage(vpn);
    				clockLastPos = i;
        			return i;
    			}
    		} else {
    			// give second chance
    			translationEntry.used = false;
    		}
    	}
    	// run a full cycle, all should be not used
    	// check if pinned
    	for(int j = clockLastPos + 1 ; j<numPhysPages+clockLastPos+1;j++) {
    		int i = j%numPhysPages;
    		VMProcess process = phyPages[i];
    		int vpn = phyPagesvpn[i];
    		if (!process.getETE(vpn).isPinned) {
    			process.evictPage(vpn);
    			clockLastPos = i;
        		return i;
    		}
    	}
    	// all page is pinned
    	//Lib.assertTrue(mainmemLock.isHeldByCurrentThread(), "mainmemLock is not held by clock()!");
    	mainmemLock.release();
    	pinWaiter.waitForPin(); // go to sleep until other process unpin any page
    	while (true) {
    		mainmemLock.acquire();
    		for(int i = 0 ; i<numPhysPages;i++) {
        		VMProcess process = phyPages[i];
        		int vpn = phyPagesvpn[i];
        		if (!process.getETE(vpn).isPinned) {
        			process.evictPage(vpn);
        			clockLastPos = i;
            		return i;
        		}
        	}
    		// still not get a page
    		mainmemLock.release();
    		pinWaiter.waitForPin();
    	}
    	
    }
    
    public static void freePhyPage(int ppn) {
    	if (ppn<0||ppn>=numPhysPages) {
    		return;
//    		Lib.assertNotReached("freePhyPage: error ppn!");
    	}
    	phyPages[ppn] = null;
    }
    
    public static PinWaiter pinWaiter;
    
    private static Random random;
    private static int tlbSize;
    public static int getTLBWritePos() {
    	return random.nextInt(tlbSize);
    }
    
    private static int clockLastPos = 0;
    
}
